Sparse Table
長さNの静的な値の列が与えられた時に、前処理O(NlogN)で、その列の上の区間に対する演算がO(1)で計算できるようになるデータ構造
使える演算は具体的にはminなど、argminもOK
結合法則: $ (a * b) * c = a * (b * c) 構築O(N log N)
各点から2ベキの長さの区間のminを計算
2^kの長さの区間は半分の長さの区間2つから定数オーダーで計算可能なので小さい方からDPする
クエリー
クエリー区間の長さより小さい最大の長さの計算済み区間を2つ使ってクエリ区間を覆う
例えば1〜7の区間に対して1〜4と4〜7で覆う
クエリ区間の最小値は2つのどちらかの区間での最小値
2次元に拡張できる